package cn.dapeng.linked;

import cn.dapeng.utils.BuilderArray;
import cn.dapeng.utils.LinkedCreator;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 链表：K个节点组内逆序调整
 * <p>
 * ①->②->③->④->⑤->⑥->⑦->⑧
 * 假设K=3，那么调整后
 * ③->②->①->⑥->⑤->④->⑦->⑧
 * <p>
 * https://leetcode.com/problems/reverse-nodes-in-k-group/submissions/1382814113/
 */
public class ReverseLinkedInKGroup {


    public static LinkedNode reverseKGroup(LinkedNode head, int k) {
        LinkedNode start = head;
        // 先找到换头后的新节点的头
        LinkedNode end = findKInGroup(start, k);
        if (end == null) {
            return head;
        }
        head = end;
        reverse(start, end);

        while (start.next != null) {
            LinkedNode bfNode = start;
            start = start.next;
            end = findKInGroup(start, k);
            if (end == null) {
                return head;
            }
            reverse(start, end);
            bfNode.next = end;
        }

        return head;
    }

    /**
     * 反转：开始节点start到指定节点end
     * <p>
     * 反转后end是这段链表的头，start是这段链表的尾巴
     *
     * @param start
     * @param end
     */
    public static void reverse(LinkedNode start, LinkedNode end) {
        end = end.next;
        LinkedNode nexe, cur = start, pre = null;
        while (cur != end) {
            nexe = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nexe;
        }
        start.next = end;
    }

    /**
     * 从start节点开始向后遍历K个节点，返回第K个节点
     *
     * @param start :   起始节点
     * @param k     :   向后遍历k个节点， 如果有，返回；如果没有，返回null
     * @return
     */
    public static LinkedNode findKInGroup(LinkedNode start, int k) {
        while (--k != 0 && start != null) {
            start = start.next;
        }
        return start;
    }

    public static void main(String[] args) {

        int testTimes = 100_0000;
        int k = 6;

        for (int i = 0; i < testTimes; i++) {
            LinkedNode h1 = LinkedCreator.createLinked(100, 40);
            int[] array = parseArray(h1);

            LinkedNode h2 = reverseKGroup(h1, k);
            int[] _array = parseArray(h2);

            if (!check(array, _array, k)) {
                System.out.println("Oops");
                break;
            }
        }


    }


    public static int[] parseArray(LinkedNode node) {
        List<Integer> list = new ArrayList<>();
        while (node != null) {
            list.add(node.value);
            node = node.next;
        }
        return Arrays.stream(list.toArray(new Integer[0])).mapToInt(t -> t).toArray();
    }

    /**
     * 对数器
     *
     * @param array
     * @param _array
     * @param k
     * @return
     */
    public static boolean check(int[] array, int[] _array, int k) {
        int size = array.length;
        int end = 0, cursor = 0;
        for (int i = 0; i < size; i++) {
            if (i % k == 0) {
                end += k;
                cursor = end;
            }

            if (i + k < size && array[i] != _array[--cursor]) {
                BuilderArray.print(array);
                BuilderArray.print(_array);
                return false;
            }

        }
        return true;
    }

}
